#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>

struct ListNode {
    int val;
    struct ListNode *next;
};
void printListNode(struct ListNode* head)
{
    struct ListNode* cur = head;
    while (cur)
    {
        printf("%d->", cur->val);
        cur = cur->next;
    }
    printf("NULL\n");
}

#if 0
struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {

    struct ListNode* cur = head, * pre = head, * slow = head;
    while (cur)
    {
        cur = cur->next;
        if (n-- <= 0)
        {
            pre = slow;
            slow = slow->next;
        }
    }

    if (slow)
    {
        if (head == pre && head == slow)////////
        {
            head = head->next;
            free(pre);
            return head;
        }
        pre->next = slow->next;
        free(slow);
    }
    else pre->next = NULL;
    return head;

}

int main()
{
    struct ListNode* STN1 = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* STN2 = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* STN3 = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* STN4 = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* STN5 = (struct ListNode*)malloc(sizeof(struct ListNode));

    STN1->val = 1;
    STN1->next = STN2;
    STN2->val = 2;
    STN2->next = NULL;
 /*   STN3->val = 3;
    STN3->next = STN4;
    STN4->val = 4;
    STN4->next = STN5;
    STN5->val = 5;
    STN5->next = NULL;*/

    struct ListNode* ret = removeNthFromEnd(STN1, 1);
    printListNode(ret);
}
#endif

struct ListNode* partition(struct ListNode* head, int x) {
    if (head == NULL)
        return head;
    struct ListNode* lesshead = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* lesstail = lesshead;
    struct ListNode* greaterhead = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* greatertail = greaterhead;

    struct ListNode* cur = head;
    while (cur)
    {
        if (cur->val < x)
        {
            lesstail->next = cur;
            lesstail = lesstail->next;
        }
        else
        {
            greatertail->next = cur;
            greatertail = greatertail->next;
        }
        cur = cur->next;
    }
    //if (greaterhead == greatertail)
    //{
    //    head = lesshead->next;
    //    free(lesshead);
    //    free(greaterhead);
    //    return head;
    //}
    greatertail->next = NULL;
    lesstail->next = greaterhead->next;
    head = lesshead->next;
    free(lesshead);
    free(greaterhead);
    return head;
}

int main()
{
    struct ListNode* STN1 = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* STN2 = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* STN3 = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* STN4 = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* STN5 = (struct ListNode*)malloc(sizeof(struct ListNode));

    STN1->val = 1;
    STN1->next = STN2;
    STN2->val = 1;
    STN2->next = NULL;
    //STN3->val = 1;
    //STN3->next = STN4;
    //STN4->val = 1;
    //STN4->next = STN5;
    //STN5->val = 1;
    //STN5->next = NULL;

    struct ListNode* ret = partition(STN1, 2);
    printListNode(ret);
}